package com.c2b.algorithm.leetcode.base;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <a href="https://leetcode.cn/problems/merge-k-sorted-lists/">合并 K 个升序链表(Merge k Sorted Lists)</a>
 * <p>给你一个链表数组，每个链表都已经按升序排列。</p>
 * <p>请你将所有链表合并到一个升序链表中，返回合并后的链表。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：lists = [[1,4,5],[1,3,4],[2,6]]
 *      输出：[1,1,2,3,4,4,5,6]
 *      解释：链表数组如下：
 *          [
 *            1->4->5,
 *            1->3->4,
 *            2->6
 *          ]
 *          将它们合并到一个有序链表中得到。
 *          1->1->2->3->4->4->5->6
 *
 * 示例 2：
 *      输入：lists = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：lists = [[]]
 *      输出：[]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *      <li>k == lists.length</li>
 *      <li>0 <= lists[i].length <= 500</li>
 *      <li>-10^4 <= lists[i][j] <= 10^4</li>
 *      <li>lists[i] 按 升序 排列</li>
 *      <li>lists[i].length 的总和不超过 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0002AddTwoNumbers_M 两数相加(Add Two Numbers)
 * @see LC0019RemoveNthNodeFromEndOfList_M 删除链表的倒数第 N 个结点(Remove Nth Node From End of List)
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @see LC0024SwapNodesInPairs_M 两两交换链表中的节点(Swap Nodes in Pairs)
 * @see LC0025ReverseNodesInKGroup_H K 个一组翻转链表(Reverse Nodes in k-Group)
 * @see LC0138CopyListWithRandomPointer_M 随机链表的复制(Copy List with Random Pointer)
 * @see LC0141LinkedListCycle_S 环形链表(Linked List Cycle)
 * @see LC0142LinkedListCycle_II_M 环形链表 II(Linked List Cycle II)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0148SortList_M 排序链表(Sort List)
 * @see LC0160IntersectionOfTwoLinkedLists_S 相交链表(Intersection of Two Linked Lists)
 * @see LC0206ReverseLinkedList_S 反转链表(Reverse Linked List)
 * @see LC0234PalindromeLinkedList_S 回文链表(Palindrome Linked List)
 * @since 2023/11/2 11:06
 */
public class LC0023MergeKSortedLists {
    static class Solution {
        /**
         * 推荐。分治合并
         *
         * @param lists 要合并的链表
         * @return 合并结果
         */
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            return merge(lists, 0, lists.length - 1);
        }

        /**
         * 合并 lists 中指定范围的链表。
         * <p>过程：每次找到 left 和 right的中点 mid，对[left,mid]合并，再对[mid+1,right]，最后再对合并后的结果合并</p>
         *
         * @param lists 数组
         * @param left  左边界
         * @param right 右边界
         * @return 合并结果
         */
        private ListNode merge(ListNode[] lists, int left, int right) {
            if (left == right) {
                return lists[left];
            }
            if (left > right) {
                return null;
            }
            int mid = left + ((right - left) >> 1);
            return merge(merge(lists, left, mid), merge(lists, mid + 1, right));
        }

        private ListNode merge(ListNode list1, ListNode list2) {
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }
            ListNode dummyHead = new ListNode(-1);
            ListNode currNode = dummyHead;
            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    currNode.next = list1;
                    list1 = list1.next;
                } else {
                    currNode.next = list2;
                    list2 = list2.next;
                }
                currNode = currNode.next;
            }
            currNode.next = list1 != null ? list1 : list2;
            return dummyHead.next;
        }

        public ListNode mergeKLists2(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            // 使用小根堆，堆中起始保留所有链表的头节点
            PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e.val));
            for (ListNode node : lists) {
                if (node != null) {
                    heap.offer(node);
                }
            }
            ListNode dummyHead = new ListNode(-1);
            ListNode currNode = dummyHead;
            while (!heap.isEmpty()) {
                ListNode minNode = heap.poll();
                currNode.next = minNode;
                currNode = currNode.next;
                if (minNode.next != null) {
                    heap.offer(minNode.next);
                }
            }
            return dummyHead.next;
        }

        public ListNode mergeKLists3(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            ListNode list1 = null;
            for (ListNode list : lists) {
                list1 = merge(list1, list);
            }
            return list1;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(4);
        head1.next.next = new ListNode(5);
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(4);
        ListNode head3 = new ListNode(2);
        head3.next = new ListNode(6);
        ListNode[] lists = {head1, head2, head3};
        Solution solution = new Solution();
        Printer.printListNode(solution.mergeKLists(lists));
        Printer.printListNode(solution.mergeKLists(null));
        Printer.printListNode(solution.mergeKLists(new ListNode[0]));
    }
}
